G

2023-05-17 16:03| 来源: 网络整理| 查看: 265

https://vjudge.net/contest/394560#problem/G

题目意思是总共有n个论文，每篇论文都有一个被接受的概率，求被接受的最大期望，提交i篇论文，被接受j篇，，，求这个的最大，，首先把概率排序，从大到小，然后用dp求前i个论文，被接受j个的概率，然后再乘以相应的题目给的公式就OK

概率的转移方程是 d [ i ] [ j ] = d [ i − 1 ] [ j ] ∗ ( 1 − a [ i ] ) + d [ i − 1 ] [ j − 1 ] ∗ a [ i ] d[i][j]=d[i-1][j]*(1-a[i])+d[i-1][j-1]*a[i] d[i][j]=d[i−1][j]∗(1−a[i])+d[i−1][j−1]∗a[i] dp[i][j]表示前i个论文成功了j个；

#include #include using namespace std; double cmp(double c,double b) { return c>b; } int main() { double a[115]; double dp[115][115]; int n; cin>>n; for(int i=1;i dp[i][0]=dp[i-1][0]*(1-a[i]); //先给前i篇，但被接受的是0篇赋值 } //因为后面会这个的基础上进行dp； for(int i=1;i //被接受j篇 dp[i][j]=dp[i-1][j]*(1-a[i])+dp[i-1][j-1]*a[i]; } //dp[i][j]= i-1篇里被接受了j篇，和被接受了j-1篇两种情况 } double res=0; for(int i=1;i //求最大 ans+=dp[i][j]*pow(j,j*1.0/(i*1.0)); } res=max(res,ans); } printf("%.9lf\n",res); return 0; }

【本文地址】

公司简介

联系我们